package main.java.indi.zyj.c150.dp;



import java.util.Scanner;

public class _04_PickMedicine {
    public static void main(String[] args) throws Exception {
        // 读入数据的代码
        Scanner reader = new Scanner(System.in);
        // 物品的数量为N
        int N = reader.nextInt();
        // 背包的容量为V
        int V = reader.nextInt();
        // 一个长度为N的数组，第i个元素表示第i个物品的体积；
        int[] v = new int[N + 1];
        // 一个长度为N的数组，第i个元素表示第i个物品的价值；
        int[] w = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            //读入是第一个数索引为1
            // 接下来有 N 行，每行有两个整数:v[i],w[i]，用空格隔开，分别表示第i件物品的体积和价值
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        reader.close();

        // 二维dp

        int[][] dp = new int[N + 1][V + 1];
        dp[0][0] = 0;
        //此处i从1开始是因为上面v[i]和w[i]是从1开始存的
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                if (j >= v[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.println(dp[N][V]);


//        //压缩为一维dp数组
//        int[] dp = new int[V + 1];
//        dp[0] = 0;
//        for (int i = 1; i <= N; i++) {
//            for (int j = V; j >= v[i]; j--) {
//                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
//            }
//        }

    }
}
